package ahaArithmetic;

//水管工游戏 深度优先解法
public class Dfs_4 {

    static int[][] map = new int[][]{
            {5,3,5,3},
            {1,5,3,0},
            {2,3,5,1},
            {6,1,1,5},
            {1,5,5,4}
    };
    static int book[][] = new int[map.length][map[0].length];
    static Node_dfs[] nodes = new Node_dfs[21];
    static int startX = 0;
    static int startY = 0;
    static int head = 0;

    public static void main(String[] args) {
        for(int i=0;i<nodes.length;i++){
            nodes[i] = new Node_dfs();
        }
        dfs_4(startX,startY,startX,startY-1,2);
    }

    //K:0,1,2,3 代表水过来的方向 上下左右
    public static void dfs_4(int x,int y,int fx,int fy,int k){
        //判断越界和障碍以及是否使用过
        if(x<0 || x>4 || y<0 || y>3 || map[x][y]==0 || book[x][y]==1){
            return;
        }
        //判断到达终点时是否成功
        if(x==4 && y==3){
            //终点为直管
            if(map[x][y]>=5){
                if(k==2){
                    print();
                    return;
                }
                else {
                    return;
                }
            }
            //终点为弯管
            else if(map[x][y]<5){
                if(k==0 || k==1){
                    print();
                    return;
                }
                else {
                    return;
                }
            }
        }
        //标记为已经走过
        book[x][y] = 1;
        nodes[head].x = x;
        nodes[head].y = y;
        head++;

        //判断下一步 直管
        if(map[x][y]>=5){
            if(k==0){
                dfs_4(x+1,y,x,y,0);
            }
            else if(k==1){
                dfs_4(x-1,y,x,y,1);
            }
            else if(k==2){
                dfs_4(x,y+1,x,y,2);
            }
            else if(k==3){
                dfs_4(x,y-1,x,y,3);
            }
        }
        //判断下一步 弯管
        else if(map[x][y] < 5){
            if(k==0 || k==1){
                dfs_4(x,y-1,x,y,3);
                dfs_4(x,y+1,x,y,2);
            }
            else if(k==2 || k==3){
                dfs_4(x-1,y,x,y,1);
                dfs_4(x+1,y,x,y,0);
            }
        }
        //判断结束 标记为未使用
        book[x][y] = 0;
        head--;
    }

    public static void print(){
        System.out.println("success: 路径如下");
        for(int i=0;i<head;i++){
            System.out.println(nodes[i].x+" "+nodes[i].y);
        }
    }
}

class Node_dfs{
    int x;
    int y;
}
